package Tree.BinarySearchTree;

import java.util.ArrayList;
import java.util.List;

/**
 * 搜索二叉树
 */
public class SearchTree {
    private Node root;

    private List<Integer> list;

    public SearchTree(int data){
        root=new Node(data);
    }

    public void insert(Node root, int data) {
        //右子树
        if (root.data < data) {
            if (root.right == null) {
                root.right = new Node(data);
            }else {
                insert(root.right,data);
            }
        }
        //左子树
        if (root.data > data) {
            if (root.left == null) {
                root.left = new Node(data);
            }else {
                insert(root.left,data);
            }
        }
    }

    public static SearchTree SearchTreeByArray(int[] array) {
        if (array.length != 0) {
            SearchTree tree = new SearchTree(array[0]);
            for (int i = 1; i < array.length; i++) {
                tree.insert(tree.root,array[i]);
            }
            return tree;
        }
        return null;
    }

    //输出 三种遍历 + 层序遍历
    public void show(String order){
        list = new ArrayList<Integer>();
        if(order.equals("before")){
            // 前序遍历
            beforeTraversal(root);
        }else if(order.equals("in")){
            // 中序遍历
            inTraversal(root);
        }else if(order.equals("after")){
            //后续遍历
            afterTraversal(root);
        }else{
            System.out.println("Order Error !");
        }

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + "\t");
        }
        System.out.println();
        list = null ;
    }
    private void beforeTraversal(Node tree) {
        if (tree != null) {
            list.add(tree.data);
            beforeTraversal(tree.left);
            beforeTraversal(tree.right);
        }
    }
    private void inTraversal(Node tree) {
        if (tree != null) {
            inTraversal(tree.left);
            list.add(tree.data);
            inTraversal(tree.right);
        }
    }
    private void afterTraversal(Node tree) {
        if (tree != null) {
            afterTraversal(tree.left);
            if (tree.right != null) {
                afterTraversal(tree.right);
            }
            list.add(tree.data);
        }
    }

    //节点个数
    public int size(){
        int ret = toSize(root,0);
        System.out.println(ret);
        return ret;
    }
    private int toSize(Node node,int count) {

        if (node == null) {
            return count;
        }
        count++;
        toSize(node.right,count);
        toSize(node.left,count);
        return count;
    }
    //宽度
    public int width(){
        int ret = toWidth(root,0);
        System.out.println(ret);
        return ret;
    }
    private int toWidth(Node root, int num) {
        if (root == null) {
            return num;
        }
        if (root.left == null && root.right == null) {
            num++;
        }
        toWidth(root.left,num);
        toWidth(root.right,num);
        return num;
    }
    public int width(int level){
        int ret = LevelWidth(root,level);
        System.out.println(ret);
        return ret;
    }
    private int LevelWidth(Node root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return LevelWidth(root.right, k - 1) + LevelWidth(root.left, k - 1);
    }

    //高度
    public int height(){
        int ret = toHeight(root);
        System.out.println(ret);
        return ret;
    }
    private int toHeight(Node root){
        if(root == null) {
            return 0;
        }
        int leftH = toHeight(root.left);
        int rightH = toHeight(root.right);
        return leftH > rightH ? leftH+1 : rightH+1;
    }

    // 检测值为value的元素是否存在
    public Node find(Node node, int val) {
        if (node == null) {
            return null;
        }
        if (node.data == val) {
            return root;
        }
        Node ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }
        ret = find(root.right, val);
        if (ret != null) {
            return ret;
        }
        return null;
    }

    //删除指定节点
    public boolean delete(int data) {
        //当前节点
        Node current = root;
        //父节点
        Node parentNode = root;
        //当前节点是否为左节点
        boolean isLeftNode = false;

        //定位data的位置
        while (current.data != data) {
            parentNode = current;
            if (current.data > data) {
                isLeftNode = true;
                current = current.left;
            } else {
                isLeftNode = false;
                current = current.right;
            }

            if (current == null) {
                return false;
            }
        }

        // 1 第一种情况 此节点为叶子节点
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftNode) {
                //如果要删除的节点为父节点的左节点 把父节点的左节点置为空
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
            return true;
        }
        //2 当前节点有一个节点
        if (current.left == null && current.right != null) {
            if (root == current) {
                root = current.right;
            } else if (isLeftNode) {
                parentNode.left = current.right;
            } else {
                parentNode.right = current.right;
            }
        } else if (current.left != null && current.right == null) {
            if (root == current) {
                root = current.left;
            } else if (isLeftNode) {
                parentNode.left = current.left;
            } else {
                parentNode.right = current.left;
            }
        }

        //3 当前节点有两个节点

        if(current.left != null && current.right != null){
            //获取删除节点的后继结点
            Node successor = getSuccessor(current);
            if (root == current) {
                root = successor;
            } else if (isLeftNode) {
                parentNode.left = successor;
            } else {
                parentNode.right = successor;
            }
        }
        return false;
    }
    private Node getSuccessor(Node delNode) {
        //获取要删除节点的后继节点
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.right;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        if (successor != delNode.right) {
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }
        return successor;
    }

}
